package demo_0405;

import java.util.*;

public class T5 {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            }else {
                map.put(word,1);
            }
        }

        PriorityQueue<Map.Entry<String,Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            // 按照出现次数升序排序
            // 如果出现次数相同，按照字符串降序排序
            // 如果出现次数不同，按照出现次数升序排序

            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().equals(o2.getValue())) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        // 遍历map，把每个元素都放到优先级队列中
        // 如果优先级队列中的元素个数小于k，就把元素放到优先级队列中
        // 如果优先级队列中的元素个数等于k，就比较优先级队列中的第一个元素和当前元素的出现次数
        // 如果优先级队列中的第一个元素的出现次数小于当前元素的出现次数，就把优先级队列中的第一个元素删除，把当前元素放到优先级队列中
        // 如果优先级队列中的第一个元素的出现次数等于当前元素的出现次数，就比较优先级队列中的第一个元素和当前元素的字符串
        // 如果优先级队列中的第一个元素的字符串小于当前元素的字符串，就把优先级队列中的第一个元素删除，把当前元素放到优先级队列中
        // 如果优先级队列中的第一个元素的字符串大于当前元素的字符串，就不做任何操作
        // 遍历结束，优先级队列中的元素就是前k个出现次数最多的元素
        // 把优先级队列中的元素放到list中
        // 把list返回
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(entry);
            } else {
                Map.Entry<String, Integer> top = priorityQueue.peek();
                if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        priorityQueue.poll();
                        priorityQueue.offer(entry);
                    }
                } else {
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        priorityQueue.poll();
                        priorityQueue.offer(entry);
                    }
                }
            }
        }

        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = priorityQueue.poll();
            list.add(top.getKey());
        }
        Collections.reverse(list);
        return list;

    }
}
